package com.gaojiawei.review;

import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

public class Review {
    public static void main(String[] args) {

    }

    public static ListNode merge(ListNode[] lists){
        if(lists == null || lists.length == 0){
            return null;
        }
        PriorityQueue<ListNode> pq = new PriorityQueue<>((l1,l2)->{
            return l1.val - l2.val;
        });
        for(ListNode node:lists){
            if(node != null){
                pq.add(node);
            }
        }
        if(pq == null || pq.isEmpty()){
            return null;
        }

        ListNode head = pq.peek();
        if(head.next != null){
            pq.add(head.next);
        }
        ListNode cur = head;
        while(pq.isEmpty()){
            cur.next = pq.poll();
            cur = cur.next;
            if(cur.next != null){
                pq.add(cur.next);
            }
        }
        return head;

    }

    public static List<Integer> preTraverse(TreeNode root){
        List<Integer> res = new LinkedList<>();
        if(root == null){
            return null;
        }
        res.add(root.val);
        res.addAll(preTraverse(root.left));
        res.addAll(preTraverse(root.right));
        return res;

    }

    public static boolean isSame(TreeNode p,TreeNode q){
        if(p == null ^ q == null){
            return false;
        }
        if(p == null || q == null){
            return true;
        }
        return p.val == q.val && isSame(p.left,q.left)&&isSame(p.right,p.right);
    }

    public static ListNode addTwo(ListNode l1,ListNode l2){
        if(l1 == null || l2 == null){
            return l1 == null ? l2:l1;
        }

        int len1 = getLen(l1);
        int len2 = getLen(l2);

        ListNode head = len1>len2 ? l1:l2;
        ListNode curl = head == l1? l1:l2;
        ListNode curs = head == l1? l2:l1;
        ListNode last = curl;

        int array = 0;
        while(curl != null && curs != null){
            int sum = curl.val + curs.val + array;
            curl.val = sum%10;
            array = sum/10;
            last = curl;
            curl = curl.next;
            curs = curs.next;

        }
        while(curl != null){
            int sum = curl.val+array;
            curl.val = sum%10;
            array = sum/10;
            last = curl;
            curl = curl.next;
            curs = curs.next;
        }
        if(array != 0){
            last.next = new ListNode(array);
        }

        return head;
    }


    public static int getLen(ListNode head){
        int res = 0;
        while(head !=null){
            res++;
            head = head.next;
        }
        return res;
    }


    public static ListNode merge2(ListNode l1,ListNode l2){
        if(l1 == null || l2 == null){
            return l1 == null? l2:l1;
        }
        ListNode head = l1.val > l2.val ? l1:l2;
        ListNode cur1 = head == l1? l1.next:l1;
        ListNode cur2 = head == l1? l2:l2.next;
        ListNode cur = head;
        while(cur1 != null && cur2 != null){
            if(cur1.val < cur2.val){
                cur.next = cur1;
                cur1 = cur1.next;
                cur = cur.next;
            }else{
                cur.next = cur2;
                cur2 = cur2.next;
                cur = cur.next;
            }
        }
        if(cur1 != null){
            cur.next =cur1;
        }else{
            cur.next = cur2;
        }
        return head;
    }





    public static class ListNode{
        int val;
        ListNode next;
        public ListNode(int val){
            this.val = val;
        }
    }

    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }
}
